Tramwaje

Limit pamięci: 128 MB

Z powodu nieustannych podwyżek cen prądu, burmistrz Bajtocji został zmuszony do ostrych cięć budżetowych, skutkiem czego od niedawna bajtockie tramwaje nie wyjeżdżają w trasy. Oczywiście wpływa to bardzo niekorzystnie na sytuację komunikacyjną w mieście, gdyż wszyscy mieszkańcy muszą się teraz kisić w zatłoczonych autobusach. Jednak jest promyk nadziei: Bajtocja ma szansę na dotację z Ministerstwa Infrastruktury Bitowej. W tym celu musi złożyć stosowny wniosek, w którego przygotowaniu bierzesz udział.

Sieć tramwajowa w Bajtocji składa się z skrzyżowań i odcinków torów; z każdego skrzyżowania można dojechać torami do dowolnego innego. Przy każdym skrzyżowaniu, do którego dochodzi tylko jeden odcinek torów, znajduje się pętla tramwajowa. Oznaczmy liczbę pętli przez . Miasto posiada tramwajów, każdy z nich ma jeździć po swojej trasie, która łączy dwie różne pętle tramwajowe i nie przechodzi dwa razy przez to samo skrzyżowanie. Trasy odpowiadające różnym tramwajom mogą przechodzić przez to samo skrzyżowanie lub odcinek torów, ale na danej pętli tramwajowej może zaczynać się lub kończyć co najwyżej jedna trasa.

Koszt prądu, który zużywa dziennie tramwaj, jest proporcjonalny do długości jego trasy. Zatem sumaryczny koszt dotacji, o którą ubiega się burmistrz, w istotny sposób zależy od ustalenia planu tras dla tramwajów. Burmistrz jest zainteresowany minimalnym i maksymalnym kosztem, które można uzyskać rozważając poprawne plany tras. Twoim zadaniem jest wyznaczyć te dwie liczby.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita () oznaczająca liczbę skrzyżowań w sieci tramwajowej. Skrzyżowania są ponumerowane liczbami od 1 do . W -tym z kolejnych wierszy znajdują się po trzy liczby całkowite , , (, , ) oznaczające numery skrzyżowań, które łączy -ty odcinek torów, oraz długość tego odcinka.

Wyjście

Na wyjściu należy wypisać dokładnie dwa wiersze. W pierwszym z nich powinna się znaleźć minimalna sumaryczna długość tras tramwajowych, którą da się uzyskać dla jakiegoś poprawnego planu. W drugim wierszu należy wypisać maksymalną sumaryczną długość tras.

Ocenianie

Jeśli Twój program poprawnie wyznacza dokładnie jedną z liczb na wyjściu, dostaniesz połowę liczby punktów za test.

Przykład

Dla danych wejściowych:

8
1 3 1
2 3 1
3 4 1
4 5 1
5 6 1
5 7 2
5 8 1

poprawną odpowiedzią jest:

4
9

Autor zadania: Tomasz Idziaszek, Tomasz Kociumaka.